{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find Closest LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findClosest"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #单词距离"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有个内含单词的超大文本文件，给定任意两个<code>不同的</code>单词，找出在这个文件中这两个单词的最短距离(相隔单词数)。如果寻找过程在这个文件中会重复多次，而每次寻找的单词不同，你能对此优化吗?</p>\n",
    "\n",
    "<p><strong>示例：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>words = [\"I\",\"am\",\"a\",\"student\",\"from\",\"a\",\"university\",\"in\",\"a\",\"city\"], word1 = \"a\", word2 = \"student\"\n",
    "<strong>输出：</strong>1</pre>\n",
    "\n",
    "<p>提示：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>words.length &lt;= 100000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-closest-lcci](https://leetcode.cn/problems/find-closest-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-closest-lcci](https://leetcode.cn/problems/find-closest-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"I\",\"am\",\"a\",\"student\",\"from\",\"a\",\"university\",\"in\",\"a\",\"city\"]\\n\"a\"\\n\"student\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findClosestLeaf(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        leaf=set()\n",
    "        q=collections.deque()\n",
    "        q.append(root)\n",
    "        #ans=float(\"inf\")\n",
    "        #ret=0\n",
    "        #level=0\n",
    "        e=collections.defaultdict(list)\n",
    "        while q:\n",
    "            n=len(q)\n",
    "            for i in range(n):\n",
    "                tp=q.popleft()\n",
    "                find=False\n",
    "                if tp.left:\n",
    "                    q.append(tp.left)\n",
    "                    e[tp.val].append(tp.left.val)\n",
    "                    e[tp.left.val].append(tp.val)\n",
    "                    find=True\n",
    "                if tp.right:\n",
    "                    q.append(tp.right)\n",
    "                    e[tp.val].append(tp.right.val)\n",
    "                    e[tp.right.val].append(tp.val)\n",
    "                    find=True\n",
    "                if not find :\n",
    "                    leaf.add(tp.val)\n",
    "                #    ret=min(ret,)\n",
    "        #print(e)\n",
    "        #print(leaf)\n",
    "        \n",
    "        q.append((0,k))\n",
    "        find=set()\n",
    "        find.add(k)\n",
    "        while q:\n",
    "            d,node=q.popleft()\n",
    "            #print(d,node)\n",
    "            if node in leaf:\n",
    "                return node\n",
    "            for i in e[node]:\n",
    "                if i not in find:\n",
    "                    find.add(i)\n",
    "                    q.append((d+1,i))\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findClosestLeaf(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        self.parents = {}\n",
    "        self.target = None\n",
    "        self.buildParents(root, k, None)\n",
    "\n",
    "        q = [self.target]\n",
    "        visited = set([])\n",
    "\n",
    "        while q:\n",
    "            cur = q.pop(0)\n",
    "            visited.add(cur)\n",
    "            if cur.left is None and cur.right is None:\n",
    "                return cur.val\n",
    "            if cur.left and cur.left not in visited: q.append(cur.left)\n",
    "            if cur.right and cur.right not in visited: q.append(cur.right)\n",
    "            pat = self.parents.get(cur, None)\n",
    "            if pat and pat not in visited: q.append(pat)\n",
    "\n",
    "    def buildParents(self, root, k, pat):\n",
    "        if root is None or self.target:\n",
    "            return\n",
    "\n",
    "        self.parents[root] = pat\n",
    "\n",
    "        if root.val == k:\n",
    "            self.target = root\n",
    "\n",
    "        self.buildParents(root.left, k, root)\n",
    "        self.buildParents(root.right, k, root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findClosestLeaf(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        self.parents = {}\n",
    "        target = self.buildParents(root, k, None)\n",
    "\n",
    "        q = [target]\n",
    "        visited = set([])\n",
    "\n",
    "        while q:\n",
    "            size = len(q)\n",
    "            for _ in range(size):\n",
    "                cur = q.pop(0)\n",
    "                visited.add(cur)\n",
    "                if cur.left is None and cur.right is None:\n",
    "                    return cur.val\n",
    "                if cur.left and cur.left not in visited: q.append(cur.left)\n",
    "                if cur.right and cur.right not in visited: q.append(cur.right)\n",
    "                pat = self.parents.get(cur, None)\n",
    "                if pat and pat not in visited: q.append(pat)\n",
    "\n",
    "\n",
    "\n",
    "    def buildParents(self, root, k, pat):\n",
    "        if root is None:\n",
    "            return None\n",
    "\n",
    "        self.parents[root] = pat\n",
    "\n",
    "        if root.val == k:\n",
    "            return root\n",
    "\n",
    "        left = self.buildParents(root.left, k, root)\n",
    "        right = self.buildParents(root.right, k, root)\n",
    "\n",
    "        return left if left else right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findClosestLeaf(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        p={}\n",
    "        def relation(cur,fa):\n",
    "            nonlocal p\n",
    "            if not cur :\n",
    "                return \n",
    "            p[cur]=fa\n",
    "            relation(cur.left,cur)\n",
    "            relation(cur.right,cur)\n",
    "            return \n",
    "        relation(root,None)\n",
    "     \n",
    "        vis=set()\n",
    "        def check(r):\n",
    "            nonlocal vis\n",
    "            if r in vis:\n",
    "                return float(\"inf\"),None\n",
    "            vis.add(r)\n",
    "            if not r.left and not r.right:\n",
    "                return 1,r.val\n",
    "            if r.left:\n",
    "                lside,lval=check(r.left)\n",
    "            else:\n",
    "                lside,lval=float(\"inf\"),None\n",
    "            if r.right:\n",
    "                rside,rval=check(r.right)\n",
    "            else:\n",
    "                rside,rval=float(\"inf\"),None\n",
    "            if p[r]!=None :\n",
    "                topside,topval=check(p[r])\n",
    "            else:\n",
    "                topside,topval=float(\"inf\"),None\n",
    "            mi=min(topside,rside,lside)\n",
    "            if lside==mi:\n",
    "                return lside+1,lval\n",
    "            elif topside==mi:\n",
    "                return topside+1,topval\n",
    "            elif rside==mi:\n",
    "                return rside+1,rval\n",
    "        ans=0\n",
    "        def find(r):\n",
    "            nonlocal ans \n",
    "            if not r:\n",
    "                return \n",
    "            if r.val ==k:\n",
    "                vis=set()\n",
    "                ans=check(r)\n",
    "                return \n",
    "            find(r.left)\n",
    "            find(r.right)\n",
    "            return \n",
    "        find(root)\n",
    "        return ans[1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findClosestLeaf(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        ret = None\n",
    "        min_d = float(\"inf\")\n",
    "        def dfs(node):\n",
    "            nonlocal ret, min_d\n",
    "            if not node.left and not node.right:\n",
    "                if node.val == k:\n",
    "                    ret = node.val\n",
    "                    min_d = 0\n",
    "                return 1, node.val, node.val == k\n",
    "            left_depth, left_lowest_leaf, left_depth_k = float(\"inf\"), None, -1\n",
    "            right_depth, right_lowest_leaf, right_depth_k = float(\"inf\"), None, -1\n",
    "            if node.left:\n",
    "                left_depth, left_lowest_leaf, left_depth_k = dfs(node.left)\n",
    "            if node.right:\n",
    "                right_depth, right_lowest_leaf, right_depth_k = dfs(node.right)\n",
    "            \n",
    "            if left_depth <= right_depth:\n",
    "                curr_depth = left_depth\n",
    "                curr_leaf = left_lowest_leaf\n",
    "            else:\n",
    "                curr_depth = right_depth\n",
    "                curr_leaf = right_lowest_leaf\n",
    "            curr_depth_k = -1\n",
    "            if node.val == k:\n",
    "                print(node.val, curr_depth, curr_leaf, left_depth, right_depth)\n",
    "                if curr_depth < min_d:\n",
    "                    min_d = curr_depth\n",
    "                    ret = curr_leaf\n",
    "                curr_depth_k = 1\n",
    "            elif left_depth_k >= 1:\n",
    "                if right_depth + left_depth_k < min_d:\n",
    "                    min_d = right_depth + left_depth_k\n",
    "                    ret = right_lowest_leaf\n",
    "                curr_depth_k = left_depth_k + 1\n",
    "            elif right_depth_k >= 1:\n",
    "                if left_depth + right_depth_k < min_d:\n",
    "                    min_d = left_depth + right_depth_k \n",
    "                    ret = left_lowest_leaf\n",
    "                curr_depth_k = right_depth_k + 1\n",
    "            # print(node.val, curr_depth, curr_leaf, curr_depth_k)\n",
    "            return curr_depth + 1, curr_leaf, curr_depth_k\n",
    "\n",
    "        dfs(root)\n",
    "\n",
    "        return ret\n",
    "\n",
    "            \n",
    "                \n",
    "                \n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "\"\"\"\n",
    "graph = {\n",
    "    1: [2, 3],\n",
    "    2: [1, 4, 5],\n",
    "    3: [1, 6, 7],\n",
    "    4: [2],\n",
    "    5: [2],\n",
    "    6: [3],\n",
    "    7: [3]\n",
    "}\n",
    "\n",
    "leaves = {4, 5, 6, 7}\n",
    "用visited去重，从1开始我们到2，然后到2后，我们可以到1，如果没有visited的话\n",
    "就会1->2, 2->1这样循环\n",
    "\n",
    "因为使用bfs, 一层一层的搜索，最早碰到的就是最近的\n",
    "\n",
    "构建graph, 如果是根节点，放入leaves。\n",
    "如果存在左节点，构建图，然后遍历左子树\n",
    "如果存在右节点，构建图，然后遍历右子树\n",
    "\n",
    "然后把目标值放入queue, 如果找到目标(leaves),就返回node\n",
    "遍历这个node的邻居，如果邻居还没访问过，就放入queue\n",
    "\"\"\"\n",
    "from collections import deque, defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def findClosestLeaf(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        leaves = set()\n",
    "        graph = defaultdict(list)\n",
    "\n",
    "        def build_graph(root):\n",
    "            if not root:\n",
    "                return\n",
    "\n",
    "            if not root.left and not root.right:\n",
    "                leaves.add(root.val)\n",
    "\n",
    "            if root.left:\n",
    "                graph[root.left.val].append(root.val)\n",
    "                graph[root.val].append(root.left.val)\n",
    "                build_graph(root.left)\n",
    "            if root.right:\n",
    "                graph[root.right.val].append(root.val)\n",
    "                graph[root.val].append(root.right.val)\n",
    "                build_graph(root.right)\n",
    "\n",
    "        build_graph(root)\n",
    "        queue = deque([k])\n",
    "        visited = set([k])\n",
    "\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "\n",
    "            if node in leaves:\n",
    "                return node\n",
    "            \n",
    "            for neighbor in graph[node]:\n",
    "                if neighbor not in visited:\n",
    "                    queue.append(neighbor)\n",
    "                    visited.add(neighbor)\n",
    "        \n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "from collections import defaultdict, deque\n",
    "\n",
    "class Solution:\n",
    "    def findClosestLeaf(self, root: Optional[TreeNode], k: int) -> int:\n",
    "\n",
    "        graph = defaultdict(list)\n",
    "        leaves = set()\n",
    "\n",
    "        def build_graph(root):\n",
    "            if not root:\n",
    "                return\n",
    "            \n",
    "            if not root.left and not root.right:  # 判断叶子节点\n",
    "                leaves.add(root.val)\n",
    "            \n",
    "            if root.left:\n",
    "                graph[root.left.val].append(root.val)\n",
    "                graph[root.val].append(root.left.val)\n",
    "                build_graph(root.left)\n",
    "            if root.right:\n",
    "                graph[root.right.val].append(root.val)\n",
    "                graph[root.val].append(root.right.val)\n",
    "                build_graph(root.right)\n",
    "        \n",
    "        build_graph(root)\n",
    "\n",
    "        queue = deque([k])\n",
    "        visited = set([k])\n",
    "        \n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if node in leaves:  # 如果该节点是叶子节点\n",
    "                return node\n",
    "            for neighbor in graph[node]:\n",
    "                if neighbor not in visited:\n",
    "                    visited.add(neighbor)\n",
    "                    queue.append(neighbor)\n",
    "        return -1  # Should not reach here as there must be a leaf in the tree\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findClosestLeaf(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        if root.left == None and root.right == None:\n",
    "            if root.val == k:\n",
    "                return root.val\n",
    "            else:\n",
    "                return -1\n",
    "        self.adjVex = defaultdict(list)\n",
    "        def dfs(node, parent):\n",
    "            if node:\n",
    "                if parent:\n",
    "                    self.adjVex[node].append(parent)\n",
    "                    self.adjVex[parent].append(node)\n",
    "                dfs(node.left, node)\n",
    "                dfs(node.right, node)\n",
    "        dfs(root,None)\n",
    "        start = None\n",
    "        for node in self.adjVex:\n",
    "            if node.val == k:\n",
    "                start = node\n",
    "                break\n",
    "        queue = [start]\n",
    "        visited = set()\n",
    "        visited.add(start)\n",
    "        while queue:\n",
    "            cur = queue.pop(0)\n",
    "            if cur.left == None and cur.right == None:\n",
    "                return  cur.val\n",
    "            for nxt in self.adjVex[cur]:\n",
    "                if nxt not in visited:\n",
    "                    visited.add(nxt)\n",
    "                    queue.append(nxt)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findClosestLeaf(self, root: Optional[TreeNode], k: int) -> int:\n",
    "\n",
    "        cache = dict()\n",
    "\n",
    "        def search(root): #  -> (TreeNode, int)\n",
    "            if root is None:\n",
    "                return None, -1\n",
    "            leaf_l, dp_l = search(root.left)\n",
    "            leaf_r, dp_r = search(root.right)\n",
    "            # print(leaf_l, dp_l, leaf_r, dp_r)\n",
    "            nearest_leaf, depth = root.val, 0\n",
    "\n",
    "            if (dp_l >=0 and dp_l<=dp_r) or (dp_r <0 and dp_l>=0):\n",
    "                nearest_leaf = leaf_l\n",
    "                depth = dp_l+1\n",
    "            elif (dp_r >=0 and dp_l>dp_r) or (dp_l <0 and dp_r >=0):\n",
    "                nearest_leaf = leaf_r\n",
    "                depth = dp_r+1\n",
    "                \n",
    "            \n",
    "            cache[root.val] = (nearest_leaf, depth)\n",
    "            return nearest_leaf, depth\n",
    "        \n",
    "        search(root)\n",
    "        print(cache)\n",
    "\n",
    "        def update(root, new_leaf, new_dp):\n",
    "            if root is None:\n",
    "                return None\n",
    "            \n",
    "            root_val = root.val\n",
    "            nearest_leaf, depth = cache[root_val]\n",
    "            if new_dp < depth:\n",
    "                nearest_leaf = new_leaf\n",
    "                depth = new_dp\n",
    "                cache[root_val] =(nearest_leaf, depth)\n",
    "            \n",
    "            if root.val == k:\n",
    "                return nearest_leaf\n",
    "\n",
    "            res_l = update(root.left, nearest_leaf, depth+1)\n",
    "            if res_l:\n",
    "                return res_l\n",
    "            res_r = update(root.right, nearest_leaf, depth+1)\n",
    "            if res_r:\n",
    "                return res_r\n",
    "        \n",
    "        leaf, root_dp = cache[root.val]\n",
    "        return update(root, leaf, root_dp)\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from collections import deque, defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def findClosestLeaf(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        leaves = set()\n",
    "        graph = defaultdict(list)\n",
    "\n",
    "        def build_graph(root):\n",
    "            if not root:\n",
    "                return\n",
    "\n",
    "            if not root.left and not root.right:\n",
    "                leaves.add(root.val)\n",
    "            \n",
    "            if root.left:\n",
    "                graph[root.left.val].append(root.val)\n",
    "                graph[root.val].append(root.left.val)\n",
    "                build_graph(root.left)\n",
    "            if root.right:\n",
    "                graph[root.right.val].append(root.val)\n",
    "                graph[root.val].append(root.right.val)\n",
    "                build_graph(root.right)\n",
    "        \n",
    "        build_graph(root)\n",
    "\n",
    "        queue = deque([k])\n",
    "        visited = set([k])\n",
    "\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "\n",
    "            if node in leaves:\n",
    "                return node\n",
    "            for neighbor in graph[node]:\n",
    "                if neighbor not in visited:\n",
    "                    queue.append(neighbor)\n",
    "                    visited.add(neighbor)\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "from collections import defaultdict, deque\n",
    "\n",
    "class Solution:\n",
    "    def findClosestLeaf(self, root: Optional[TreeNode], k: int) -> int:\n",
    "\n",
    "        graph = defaultdict(list)\n",
    "        leaves = set()\n",
    "\n",
    "        def build_graph(root):\n",
    "            if not root:\n",
    "                return\n",
    "            \n",
    "            if not root.left and not root.right:  # 判断叶子节点\n",
    "                leaves.add(root.val)\n",
    "            \n",
    "            if root.left:\n",
    "                graph[root.left.val].append(root.val)\n",
    "                graph[root.val].append(root.left.val)\n",
    "                build_graph(root.left)\n",
    "            if root.right:\n",
    "                graph[root.right.val].append(root.val)\n",
    "                graph[root.val].append(root.right.val)\n",
    "                build_graph(root.right)\n",
    "        \n",
    "        build_graph(root)\n",
    "\n",
    "        queue = deque([k])\n",
    "        visited = set([k])\n",
    "        \n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if node in leaves:  # 如果该节点是叶子节点\n",
    "                return node\n",
    "            for neighbor in graph[node]:\n",
    "                if neighbor not in visited:\n",
    "                    visited.add(neighbor)\n",
    "                    queue.append(neighbor)\n",
    "        return -1  # Should not reach here as there must be a leaf in the tree\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "\"\"\"\n",
    "graph = {\n",
    "    1: [2, 3],\n",
    "    2: [1, 4, 5],\n",
    "    3: [1, 6, 7],\n",
    "    4: [2],\n",
    "    5: [2],\n",
    "    6: [3],\n",
    "    7: [3]\n",
    "}\n",
    "\n",
    "leaves = {4, 5, 6, 7}\n",
    "用visited去重，从1开始我们到2，然后到2后，我们可以到1，如果没有visited的话\n",
    "就会1->2, 2->1这样循环\n",
    "\n",
    "因为使用bfs, 一层一层的搜索，最早碰到的就是最近的\n",
    "\n",
    "构建graph, 如果是根节点，放入leaves。\n",
    "如果存在左节点，构建图，然后遍历左子树\n",
    "如果存在右节点，构建图，然后遍历右子树\n",
    "\n",
    "然后把目标值放入queue, 如果找到目标(leaves),就返回node\n",
    "遍历这个node的邻居，如果邻居还没访问过，就放入queue\n",
    "\"\"\"\n",
    "from collections import deque, defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def findClosestLeaf(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        leaves = []\n",
    "        graph = defaultdict(list)\n",
    "\n",
    "        def build_graph(root):\n",
    "            if not root:\n",
    "                return\n",
    "\n",
    "            if not root.left and not root.right:\n",
    "                leaves.append(root.val)\n",
    "\n",
    "            if root.left:\n",
    "                graph[root.left.val].append(root.val)\n",
    "                graph[root.val].append(root.left.val)\n",
    "                build_graph(root.left)\n",
    "            if root.right:\n",
    "                graph[root.right.val].append(root.val)\n",
    "                graph[root.val].append(root.right.val)\n",
    "                build_graph(root.right)\n",
    "\n",
    "        build_graph(root)\n",
    "        queue = deque([k])\n",
    "        visited = set([k])\n",
    "\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "\n",
    "            if node in leaves:\n",
    "                return node\n",
    "            \n",
    "            for neighbor in graph[node]:\n",
    "                if neighbor not in visited:\n",
    "                    queue.append(neighbor)\n",
    "                    visited.add(neighbor)\n",
    "        \n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findClosestLeaf(self, root: Optional[TreeNode], k: int) -> int:\n",
    "\n",
    "        graph = collections.defaultdict(list)\n",
    "        \n",
    "        def dfs(node, par = None):\n",
    "            if node:\n",
    "                graph[node].append(par)\n",
    "                graph[par].append(node)\n",
    "                dfs(node.left, node)\n",
    "                dfs(node.right, node)\n",
    "        \n",
    "        dfs(root)\n",
    "        que = collections.deque(node for node in graph if node and node.val == k)\n",
    "        seen = set(que)\n",
    "        while que:\n",
    "\n",
    "            node = que.popleft()\n",
    "            if node:\n",
    "                # 叶子结点\n",
    "                if len(graph[node]) <= 1:\n",
    "                    return node.val\n",
    "                \n",
    "                for nei in graph[node]:\n",
    "                    if nei not in seen:\n",
    "                        seen.add(nei)\n",
    "                        que.append(nei)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findClosestLeaf(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        graph=defaultdict(list)\n",
    "        def getGraph(root:Optional[TreeNode],parent:Optional[TreeNode]=None):\n",
    "            if root:\n",
    "                graph[root].append(parent)\n",
    "                graph[parent].append(root)\n",
    "                getGraph(root.left,root)\n",
    "                getGraph(root.right,root)\n",
    "        getGraph(root)\n",
    "        queue=deque(n for n in graph if n and n.val==k )\n",
    "        visited=set(queue)\n",
    "        while queue:\n",
    "            cur=queue.popleft()\n",
    "            if cur:\n",
    "                # 叶子结点，只有父节点可到达\n",
    "                if len(graph[cur])<=1:\n",
    "                    return cur.val\n",
    "                for adj in graph[cur]:\n",
    "                    if adj not in visited:\n",
    "                        visited.add(adj)\n",
    "                        queue.append(adj)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution(object):\n",
    "    def findClosestLeaf(self, root, k):\n",
    "        graph = collections.defaultdict(list)\n",
    "        def dfs(node, par = None):\n",
    "            if node:\n",
    "                graph[node].append(par)\n",
    "                graph[par].append(node)\n",
    "                dfs(node.left, node)\n",
    "                dfs(node.right, node)\n",
    "\n",
    "        dfs(root)\n",
    "        queue = collections.deque(node for node in graph\n",
    "                                  if node and node.val == k)\n",
    "        seen = set(queue)\n",
    "\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if node:\n",
    "                if len(graph[node]) <= 1:\n",
    "                    return node.val\n",
    "                for nei in graph[node]:\n",
    "                    if nei not in seen:\n",
    "                        seen.add(nei)\n",
    "                        queue.append(nei)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findClosestLeaf(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        if root.left == None and root.right == None:            #只有一个点，无法建图\n",
    "            if root.val == k:\n",
    "                return root.val\n",
    "            else:\n",
    "                return -1\n",
    "        head = 0\n",
    "        tail = 0\n",
    "        self.graph = defaultdict(list)\n",
    "        print(self.graph)\n",
    "        def dfs(node,parent):\n",
    "            if node:\n",
    "                if parent:\n",
    "                    self.graph[node].append(parent)\n",
    "                    self.graph[parent].append(node)\n",
    "                dfs(node.left, node)\n",
    "                dfs(node.right, node)\n",
    "        dfs(root, None)\n",
    "        for node in self.graph:\n",
    "            if node.val == k:\n",
    "                start = node\n",
    "\n",
    "        queue = [start]\n",
    "        visited = [start]\n",
    "        while head<=tail:\n",
    "            jl = queue[head]\n",
    "            if not jl.left and not jl.right:\n",
    "                    return jl.val\n",
    "            for node in self.graph[jl]:\n",
    "\n",
    "                if node not in visited:\n",
    "                    visited.append(node)\n",
    "                    queue.append(node)\n",
    "                    tail+=1\n",
    "            head+=1        \n",
    "        \n",
    "        return\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findClosestLeaf(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        if not root.left and not root.right:\n",
    "            return root.val\n",
    "        graph = defaultdict(list)\n",
    "\n",
    "        def dfs(node, parent = None):\n",
    "            if node:\n",
    "                graph[node].append(parent)\n",
    "                graph[parent].append(node)\n",
    "                dfs(node.left, node)\n",
    "                dfs(node.right, node)\n",
    "        \n",
    "        dfs(root)\n",
    "\n",
    "        queue = deque(node for node in graph if node and node.val == k)\n",
    "        visited = set(queue)\n",
    "\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if node:\n",
    "                if len(graph[node]) <= 1:\n",
    "                    return node.val\n",
    "            \n",
    "                for neighbor in graph[node]:\n",
    "                    if neighbor not in visited:\n",
    "                        visited.add(neighbor)\n",
    "                        queue.append(neighbor)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def findClosestLeaf(self, root, k):\n",
    "        graph = collections.defaultdict(list)\n",
    "        def dfs(node, par = None):\n",
    "            if node:\n",
    "                graph[node].append(par)\n",
    "                graph[par].append(node)\n",
    "                dfs(node.left, node)\n",
    "                dfs(node.right, node)\n",
    "\n",
    "        dfs(root)\n",
    "        queue = collections.deque(node for node in graph\n",
    "                                  if node and node.val == k)\n",
    "        seen = set(queue)\n",
    "\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if node:\n",
    "                if len(graph[node]) <= 1:\n",
    "                    return node.val\n",
    "                for nei in graph[node]:\n",
    "                    if nei not in seen:\n",
    "                        seen.add(nei)\n",
    "                        queue.append(nei)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findClosestLeaf(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        graph = collections.defaultdict(list)\n",
    "        s=set()\n",
    "        def dfs(node, par):\n",
    "            if node:\n",
    "                graph[node.val].append(par)\n",
    "                graph[par.val].append(node)\n",
    "                dfs(node.left, node)\n",
    "                dfs(node.right, node)\n",
    "                if node.left==None and node.right==None:\n",
    "                    s.add(node.val)\n",
    "        dfs(root,root)\n",
    "        if k in s:\n",
    "            return k\n",
    "        q=deque()\n",
    "        vis=set()\n",
    "        vis.add(k)\n",
    "        for i in graph[k]:\n",
    "            if i.val in s:\n",
    "                return i.val\n",
    "            q.append(i)\n",
    "            vis.add(i.val)\n",
    "        while q:\n",
    "            size=len(q)\n",
    "            for i in range(size):\n",
    "                temp=q.popleft()\n",
    "                for j in graph[temp.val]:\n",
    "                    if j.val in s:\n",
    "                        return j.val\n",
    "                    if j.val not in vis:\n",
    "                        q.append(j)\n",
    "                        vis.add(j.val)\n",
    "        return -1\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections  import defaultdict\n",
    "from collections import deque\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findClosestLeaf(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        graph=defaultdict(list)\n",
    "        def dfs(root:Optional[TreeNode],parent:Optional[TreeNode]):\n",
    "            if root:\n",
    "                graph[root].append(parent)\n",
    "                graph[parent].append(root)\n",
    "                dfs(root.left,root)\n",
    "                dfs(root.right,root)\n",
    "        dfs(root,None)\n",
    "        queue=deque(node for node in graph if node and node.val==k)\n",
    "        visited=set(queue)\n",
    "        while queue:\n",
    "            cur=queue.popleft()\n",
    "            if cur:\n",
    "                if len(graph[cur])<=1:\n",
    "                    return cur.val\n",
    "                for nei in graph[cur]:\n",
    "                    if nei not in visited:\n",
    "                        visited.add(nei)\n",
    "                        queue.append(nei)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findClosestLeaf(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        graph = collections.defaultdict(list)\n",
    "        check=False\n",
    "        def dfs(node, par):\n",
    "            nonlocal check\n",
    "            if node:\n",
    "                graph[node.val].append(par)\n",
    "                graph[par.val].append(node)\n",
    "                dfs(node.left, node)\n",
    "                dfs(node.right, node)\n",
    "                if node.left==None and node.right==None and node.val==k:\n",
    "                    check=True\n",
    "        dfs(root,root)\n",
    "        if check:\n",
    "            return k\n",
    "        q=deque()\n",
    "        vis=set()\n",
    "        vis.add(k)\n",
    "        for i in graph[k]:\n",
    "            if not i.left and not i.right:\n",
    "                return i.val\n",
    "            q.append(i)\n",
    "            vis.add(i.val)\n",
    "        while q:\n",
    "            size=len(q)\n",
    "            for i in range(size):\n",
    "                temp=q.popleft()\n",
    "                for j in graph[temp.val]:\n",
    "                    if not j.left and not j.right:\n",
    "                        return j.val\n",
    "                    if j.val not in vis:\n",
    "                        q.append(j)\n",
    "                        vis.add(j.val)\n",
    "        return -1\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findClosestLeaf(self, root: Optional[TreeNode], k: int) -> int:\n",
    "\n",
    "\n",
    "        graph = collections.defaultdict(list)\n",
    "        \n",
    "        def dfs(node, par = None):\n",
    "            if node:\n",
    "                graph[node].append(par)\n",
    "                graph[par].append(node)\n",
    "                dfs(node.left, node)\n",
    "                dfs(node.right, node)\n",
    "        \n",
    "        dfs(root)\n",
    "        que = collections.deque(node for node in graph if node and node.val == k)\n",
    "        seen = set(que)\n",
    "        while que:\n",
    "\n",
    "            node = que.popleft()\n",
    "            if node:\n",
    "                if len(graph[node]) <= 1:\n",
    "                    return node.val\n",
    "                \n",
    "                for nei in graph[node]:\n",
    "                    if nei not in seen:\n",
    "                        seen.add(nei)\n",
    "                        que.append(nei)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findClosestLeaf(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        g = defaultdict(list)\n",
    "        q = deque()\n",
    "        vis = set()\n",
    "        def dfs(root):\n",
    "            if root:\n",
    "                if root.val == k and not q:\n",
    "                    q.append(root)\n",
    "                    vis.add(root)\n",
    "                if root.left:\n",
    "                    g[root].append(root.left)\n",
    "                    g[root.left].append(root)\n",
    "                if root.right:\n",
    "                    g[root].append(root.right)\n",
    "                    g[root.right].append(root)\n",
    "                dfs(root.left)\n",
    "                dfs(root.right)\n",
    "        \n",
    "        dfs(root)\n",
    "        \n",
    "        while q:\n",
    "            root = q.popleft()\n",
    "            if not root.left and not root.right:\n",
    "                return root.val\n",
    "            for nx in g[root]:\n",
    "                if nx not in vis:\n",
    "                    vis.add(nx)\n",
    "                    q.append(nx)\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findClosestLeaf(self, root: Optional[TreeNode], k: int) -> int:\n",
    "\n",
    "        graph = collections.defaultdict(list)\n",
    "        \n",
    "        def dfs(node, par = None):\n",
    "            if node:\n",
    "                graph[node].append(par)\n",
    "                graph[par].append(node)\n",
    "                dfs(node.left, node)\n",
    "                dfs(node.right, node)\n",
    "        \n",
    "        dfs(root)\n",
    "        que = collections.deque(node for node in graph if node and node.val == k)\n",
    "        seen = set(que)\n",
    "        while que:\n",
    "\n",
    "            node = que.popleft()\n",
    "            if node:\n",
    "                # 叶子结点\n",
    "                if len(graph[node]) <= 1:\n",
    "                    return node.val\n",
    "                \n",
    "                for nei in graph[node]:\n",
    "                    if nei not in seen:\n",
    "                        seen.add(nei)\n",
    "                        que.append(nei)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "        res = inf \n",
    "        idx1 = -inf\n",
    "        idx2 = -inf\n",
    "        for i in range(len(words)):\n",
    "            if words[i] == word1:\n",
    "                idx1 = i\n",
    "                res = min(i-idx2, res)\n",
    "            if words[i] == word2:\n",
    "                idx2 = i\n",
    "                print(idx2)\n",
    "                res = min(i-idx1, res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "\n",
    "        idx1, idx2, ans = -1, -1, 100000\n",
    "        for i, word in enumerate(words):\n",
    "            if word == word1:\n",
    "                idx1 = i\n",
    "            if word == word2:\n",
    "                idx2 = i\n",
    "            if idx1 != -1 and idx2 != -1:\n",
    "                ans = min(ans, abs(idx1 - idx2))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "        pos1, pos2, ret = -1, -1, len(words)\n",
    "        for i in range(len(words)):\n",
    "            if word1 == words[i]:\n",
    "                pos1 = i\n",
    "            if word2 == words[i]:\n",
    "                pos2 = i\n",
    "            if pos1 > 0 and pos2 > 0:\n",
    "                ret = min(ret, abs(pos1 - pos2))\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "        # method 1\n",
    "        # idx1 = []\n",
    "        # idx2 = []\n",
    "        # for i in range(0, len(words)):\n",
    "        #     if words[i] == word1:\n",
    "        #         idx1.append(i)\n",
    "        #     if words[i] == word2:\n",
    "        #         idx2.append(i)\n",
    "\n",
    "        # min_d = len(words)\n",
    "        # for i in idx1:\n",
    "        #     for j in idx2:\n",
    "        #         dis = abs(i-j)\n",
    "        #         if dis < min_d:\n",
    "        #             min_d = dis\n",
    "\n",
    "        # return min_d\n",
    "\n",
    "        # method 2\n",
    "        last_word = \"\"\n",
    "        last_word_pos = 0\n",
    "        dis_min = len(words)\n",
    "        for i in range(0, len(words)):\n",
    "            if words[i] == word1 or words[i] == word2:\n",
    "                if last_word == \"\":\n",
    "                    last_word = words[i]\n",
    "                    last_word_pos = i\n",
    "                else:\n",
    "                    if last_word == words[i]:\n",
    "                        last_word_pos = i\n",
    "                    else:\n",
    "                        if abs(i - last_word_pos) < dis_min:\n",
    "                            dis_min = abs(i - last_word_pos)\n",
    "                        last_word = words[i]\n",
    "                        last_word_pos = i\n",
    "        return dis_min"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "        # method 1\n",
    "        # idx1 = []\n",
    "        # idx2 = []\n",
    "        # for i in range(0, len(words)):\n",
    "        #     if words[i] == word1:\n",
    "        #         idx1.append(i)\n",
    "        #     if words[i] == word2:\n",
    "        #         idx2.append(i)\n",
    "        # min_d = len(words)\n",
    "        # for i in idx1:\n",
    "        #     for j in idx2:\n",
    "        #         dis = abs(i-j)\n",
    "        #         if dis < min_d:\n",
    "        #             min_d = dis\n",
    "        # return min_d\n",
    "\n",
    "        # method 2\n",
    "        last_word = \"\"\n",
    "        last_word_pos = 0\n",
    "        dis_min = len(words)\n",
    "        for i in range(0, len(words)):\n",
    "            if words[i] == word1 or words[i] == word2:\n",
    "                if last_word == \"\":\n",
    "                    last_word = words[i]\n",
    "                    last_word_pos = i\n",
    "                else:\n",
    "                    if last_word == words[i]:\n",
    "                        last_word_pos = i\n",
    "                    else:\n",
    "                        if abs(i - last_word_pos) < dis_min:\n",
    "                            dis_min = abs(i - last_word_pos)\n",
    "                        last_word = words[i]\n",
    "                        last_word_pos = i\n",
    "        return dis_min"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "        ans,a,b = inf,inf,-inf\n",
    "        for i,word in enumerate(words):\n",
    "            if word == word1:\n",
    "                a = i\n",
    "            elif word == word2:\n",
    "                b = i\n",
    "            ans = min(ans,abs(b-a))\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "        idx1 = []\n",
    "        idx2 = []\n",
    "        for i in range(0, len(words)):\n",
    "            if words[i] == word1:\n",
    "                idx1.append(i)\n",
    "            if words[i] == word2:\n",
    "                idx2.append(i)\n",
    "\n",
    "        min_d = len(words)\n",
    "        for i in idx1:\n",
    "            for j in idx2:\n",
    "                dis = abs(i-j)\n",
    "                if dis < min_d:\n",
    "                    min_d = dis\n",
    "\n",
    "        return min_d\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "        ans=inf\n",
    "        idx1=-inf\n",
    "        idx2=-inf\n",
    "        for i,word in enumerate(words):\n",
    "            if word1==word:\n",
    "                idx1=i\n",
    "            elif word2==word:\n",
    "                idx2=i\n",
    "            ans=min(ans,abs(idx1-idx2))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "\t\tans = len(words)\n",
    "\t\tindex1, index2 = -1, -1\n",
    "\t\tfor i, word in enumerate(words):\n",
    "\t\t\tif word == word1:\n",
    "\t\t\t\tindex1 = i\n",
    "\t\t\telif word == word2:\n",
    "\t\t\t\tindex2 = i\n",
    "\t\t\tif index1 >= 0 and index2 >= 0:\n",
    "\t\t\t\tans = min(ans, abs(index1 - index2))\n",
    "\t\treturn ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "        # 单次遍历+维护两最后下标\n",
    "        i1, i2 = -1, -1\n",
    "        res = float(\"inf\")\n",
    "        for i, w in enumerate(words):\n",
    "            if w == word1:\n",
    "                # 更新单词1最后出现下标\n",
    "                i1 = i\n",
    "                if i2 != -1:\n",
    "                    # 单词2前面出现过, 得到一个有效距离, 用它更新最终结果\n",
    "                    res = min(res, i1 - i2)\n",
    "            elif w == word2:\n",
    "                # 更新单词2最后出现下标\n",
    "                i2 = i\n",
    "                if i1 != -1:\n",
    "                    # 单词1前面出现过, 得到一个有效距离, 用它更新最终结果\n",
    "                    res = min(res, i2 - i1)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "        ans=len(words)\n",
    "        index1=-1\n",
    "        index2=-1\n",
    "        for i,word in enumerate(words):\n",
    "            if word==word1:\n",
    "                index1=i\n",
    "            elif word==word2:\n",
    "                index2=i\n",
    "            \n",
    "            if index1>=0 and index2>=0:\n",
    "                ans=min(ans,abs(index1-index2))\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "        acc1,acc2,res = -1,-1,inf\n",
    "        for i in range(len(words)):\n",
    "            if words[i]==word1:\n",
    "                acc1=i\n",
    "            if words[i]==word2:\n",
    "                acc2=i\n",
    "            if acc1>=0 and acc2>=0:\n",
    "                res = min(res,abs(acc1-acc2))\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "\n",
    "        idx1, idx2, ans = -1, -1, 100000\n",
    "        for i, word in enumerate(words):\n",
    "            if word == word1:\n",
    "                idx1 = i\n",
    "            if word == word2:\n",
    "                idx2 = i\n",
    "            if idx1 != -1 and idx2 != -1:\n",
    "                ans = min(ans, abs(idx1 - idx2))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "        acc1,acc2,res = -1,-1,inf\n",
    "        for i in range(len(words)):\n",
    "            if words[i]==word1:\n",
    "                acc1=i\n",
    "            if words[i]==word2:\n",
    "                acc2=i\n",
    "            if acc1>=0 and acc2>=0:\n",
    "                res = min(res,abs(acc1-acc2))\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\r\n",
    "        i, j = words.index(word1), words.index(word2)\r\n",
    "        n = len(words)\r\n",
    "        mindist = inf\r\n",
    "        while i < n and j < n:\r\n",
    "            if words[i] == word1 and words[j] == word2:\r\n",
    "                mindist = min(mindist, abs(j - i))\r\n",
    "                if i < j:\r\n",
    "                    i += 1\r\n",
    "                else:\r\n",
    "                    j += 1\r\n",
    "            elif words[i] == word1:\r\n",
    "                j += 1\r\n",
    "            else:\r\n",
    "                i += 1\r\n",
    "        return mindist\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "        n = len(words)\n",
    "        arr1 = []\n",
    "        arr2 = []\n",
    "        for i in range(n):\n",
    "            if words[i] == word1:\n",
    "                arr1.append(i)\n",
    "            elif words[i] == word2:\n",
    "                arr2.append(i)\n",
    "        m, r = len(arr1), len(arr2)\n",
    "        ans = inf\n",
    "        ptr = 0\n",
    "        for i in range(m):\n",
    "            while ptr < r:\n",
    "                if arr2[ptr] > arr1[i]:\n",
    "                    ans = min(ans, arr2[ptr] - arr1[i])\n",
    "                    break\n",
    "                else:\n",
    "                    ans = min(ans, arr1[i] - arr2[ptr])\n",
    "                    ptr += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "[\"I\",\"am\"]\n",
    "\"I\"\n",
    "\"am\"\n",
    "[\"I\",\"am\",\"a\",\"student\",\"from\",\"a\",\"university\",\"in\",\"a\",\"city\"]\n",
    "\"a\"\n",
    "\"student\"\n",
    "\n",
    "words.length <= 100000\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "        res = float('inf')\n",
    "        idx1, idx2 = None, None\n",
    "        for i, w in enumerate(words):\n",
    "            if word1 == w: idx1 = i\n",
    "            elif word2 == w: idx2 = i\n",
    "            if idx1 is not None and idx2 is not None:\n",
    "                res = min(res, abs(idx1-idx2))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "        res = 99999999\n",
    "        p1 = -1\n",
    "        p2 = -1\n",
    "        for i in range(len(words)):\n",
    "            if words[i] == word1:\n",
    "                p1 = i\n",
    "            if words[i] == word2:\n",
    "                p2 = i\n",
    "            if p1 !=-1 and p2 !=-1:\n",
    "                res = min(res,abs(p1-p2))\n",
    "\n",
    "\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "        if word1 == word2: return 0\n",
    "        \n",
    "        i = j = 0\n",
    "        min_dist = sys.maxsize\n",
    "        while i < len(words) and j < len(words):\n",
    "            if words[i] == word1 and words[j] == word2:\n",
    "                min_dist = min(min_dist, abs(i - j))\n",
    "                if i < j: i += 1\n",
    "                else: j += 1\n",
    "            else:\n",
    "                if words[i] != word1: i += 1\n",
    "                if words[j] != word2: j += 1\n",
    "        return min_dist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "        ans=len(words)\n",
    "        index1,index2=-1,-1\n",
    "        for i,word in enumerate(words):\n",
    "            if word==word1:\n",
    "                index1=i\n",
    "            elif word==word2:\n",
    "                index2=i\n",
    "            if index1>=0 and index2>=0:\n",
    "                ans=min(ans,abs(index1-index2))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "        idx1,idx2=-1,-1\n",
    "        ans=float(\"inf\")\n",
    "        for i,word in enumerate(words):\n",
    "            if word==word1:\n",
    "                idx1=i\n",
    "            if word==word2:\n",
    "                idx2=i\n",
    "            if idx1>=0 and idx2>=0:\n",
    "                ans=min(ans,abs(idx1-idx2))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "        if word1 == word2: return 0\n",
    "        \n",
    "        i = j = 0\n",
    "        min_dist = sys.maxsize\n",
    "        while i < len(words) and j < len(words):\n",
    "            if words[i] == word1 and words[j] == word2:\n",
    "                min_dist = min(min_dist, abs(i - j))\n",
    "                if i < j: i += 1\n",
    "                else: j += 1\n",
    "            else:\n",
    "                if words[i] != word1: i += 1\n",
    "                if words[j] != word2: j += 1\n",
    "        return min_dist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "        i, j = 0, 0\n",
    "        ans = float('inf')\n",
    "        while i < len(words) and j < len(words):\n",
    "            if words[i] != word1:\n",
    "                i += 1\n",
    "            elif words[j] != word2:\n",
    "                j += 1\n",
    "            else:\n",
    "                if i > j:\n",
    "                    ans = min(ans, abs(i - j))\n",
    "                    j += 1\n",
    "                else:\n",
    "                    ans = min(ans, abs(i - j))\n",
    "                    i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "        ans = inf\n",
    "        ind1 = inf\n",
    "        ind2 = inf\n",
    "\n",
    "        for i, word in enumerate(words):\n",
    "            if word == word1:\n",
    "                ind1 = i\n",
    "                ans = min(ans, abs(ind1-ind2))\n",
    "            elif word == word2:\n",
    "                ind2 = i\n",
    "                ans = min(ans, abs(ind1-ind2))\n",
    "        \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "        acc1,acc2 = [],[]\n",
    "        for i in range(len(words)):\n",
    "            if words[i]==word1:\n",
    "                acc1.append(i)\n",
    "            if words[i]==word2:\n",
    "                acc2.append(i)\n",
    "        m,n = len(acc1),len(acc2)\n",
    "        i,j,res = 0,0,inf\n",
    "        while i<m and j<n:\n",
    "            if acc1[i]>acc2[j]:\n",
    "                res = min(res,acc1[i]-acc2[j])\n",
    "                j+=1\n",
    "            else:\n",
    "                res = min(res,acc2[j]-acc1[i])\n",
    "                i+=1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "        acc1,acc2 = [],[]\n",
    "        for i in range(len(words)):\n",
    "            if words[i]==word1:\n",
    "                acc1.append(i)\n",
    "            if words[i]==word2:\n",
    "                acc2.append(i)\n",
    "        m,n = len(acc1),len(acc2)\n",
    "        i,j,res = 0,0,inf\n",
    "        while i<m and j<n:\n",
    "            if acc1[i]>acc2[j]:\n",
    "                res = min(res,acc1[i]-acc2[j])\n",
    "                j+=1\n",
    "            else:\n",
    "                res = min(res,acc2[j]-acc1[i])\n",
    "                i+=1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "        idxs = [-1, -1]\n",
    "        res = len(words)\n",
    "        for i in range(len(words)):\n",
    "            if words[i] == word1:\n",
    "                idxs[0] = i \n",
    "            if words[i] == word2: \n",
    "                idxs[1] = i \n",
    "            if idxs[0]!=-1 and idxs[1]!=-1:\n",
    "                res = min(res, abs(idxs[0]-idxs[1]))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "        n=len(words)\n",
    "        l1,l2=-1,-1\n",
    "        ans=100001\n",
    "        for i in range(n):\n",
    "            if words[i] == word1:\n",
    "                l1=i\n",
    "            if words[i] == word2:\n",
    "                l2=i\n",
    "            ans=min(ans,abs(l2-l1)) if l1!=-1 and l2!=-1 else ans\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "        acc1,acc2,res = -1,-1,inf\n",
    "        for i in range(len(words)):\n",
    "            if words[i]==word1:\n",
    "                acc1=i\n",
    "            if words[i]==word2:\n",
    "                acc2=i\n",
    "            if acc1>=0 and acc2>=0:\n",
    "                res = min(res,abs(acc1-acc2))\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "        stack =[]\n",
    "        ans = len(words)\n",
    "        for i in range(len(words)):\n",
    "            if words[i] == word1 or words[i] ==  word2:\n",
    "                if stack:\n",
    "                    if words[stack[-1]] == words[i]:\n",
    "                        \n",
    "                        stack.pop()\n",
    "                        stack.append(i)\n",
    "                    else:\n",
    "                        ans = min(ans,i-stack[-1])\n",
    "                        stack.pop()\n",
    "                        stack.append(i)\n",
    "                else:\n",
    "                    stack.append(i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "        dic = defaultdict(list)\n",
    "        for i in range(len(words)):\n",
    "            if words[i] == word1 or words[i] == word2:\n",
    "                dic[words[i]].append(i)\n",
    "        l1 = dic[word1]\n",
    "        l2 = dic[word2]\n",
    "        ans = inf\n",
    "        for v in l1:\n",
    "            for k in l2:\n",
    "                ans = min(ans, abs(v-k))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "\n",
    "        word1_index_list= []\n",
    "        word2_index_list = []\n",
    "        for i, w in enumerate(words):\n",
    "            if w == word1:\n",
    "                word1_index_list.append(i)\n",
    "            elif w == word2:\n",
    "                word2_index_list.append(i)\n",
    "        if not word1_index_list or not word2_index_list:\n",
    "            return -1\n",
    "        ans = inf\n",
    "        for i in word1_index_list:\n",
    "            for j in word2_index_list:\n",
    "                t =  abs(i-j)\n",
    "                if t == 1:\n",
    "                    return 1\n",
    "                ans = min(ans, t)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "        idx1, idx2 = float(\"-inf\"), float(\"inf\")\n",
    "        res = len(words)\n",
    "        for idx, word in enumerate(words):\n",
    "            if word == word1:\n",
    "                idx1 = idx\n",
    "            elif word == word2:\n",
    "                idx2 = idx\n",
    "            res = min(res, abs(idx1-idx2))\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "        acc1,acc2,res = -1,-1,inf\n",
    "        for i in range(len(words)):\n",
    "            if words[i]==word1:\n",
    "                acc1=i\n",
    "            if words[i]==word2:\n",
    "                acc2=i\n",
    "            if acc1>=0 and acc2>=0:\n",
    "                res = min(res,abs(acc1-acc2))\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "        n = len(words)\n",
    "        index1, index2 = -1, -1\n",
    "        i, res = 0, float('inf')\n",
    "        while i < n:\n",
    "            if words[i] == word1:\n",
    "                index1 = i\n",
    "            elif words[i] == word2:\n",
    "                index2 = i\n",
    "            if index1 != -1 and index2 != -1:\n",
    "                res = min(res, abs(index1-index2))\n",
    "            i += 1\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "        ans = len(words)\n",
    "        index1, index2 = 0, 0\n",
    "        for i, word in enumerate(words):\n",
    "            if word == word1:\n",
    "                index1 = i\n",
    "            if word == word2:\n",
    "                index2 = i\n",
    "            \n",
    "            if index1 > 0 and index2 > 0:\n",
    "                ans = min(ans, abs(index1 - index2))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "        p1, p2 = -1, -1\n",
    "        res = inf\n",
    "        for i, word in enumerate(words):\n",
    "            if word == word1:\n",
    "                p1 = i\n",
    "                if p2 >= 0:\n",
    "                    res = min(res, p1 - p2)\n",
    "            elif word == word2:\n",
    "                p2 = i\n",
    "                if p1 >= 0:\n",
    "                    res = min(res, p2 - p1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "        acc1,acc2,res = -1,-1,inf\n",
    "        for i in range(len(words)):\n",
    "            if words[i]==word1:\n",
    "                acc1=i\n",
    "            if words[i]==word2:\n",
    "                acc2=i\n",
    "            if acc1>=0 and acc2>=0:\n",
    "                res = min(res,abs(acc1-acc2))\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "        idx1, idx2, ans = -1, -1, 100000\n",
    "        for i, word in enumerate(words):\n",
    "            if word == word1:\n",
    "                idx1 = i\n",
    "            if word == word2:\n",
    "                idx2 = i\n",
    "            if idx1 != -1 and idx2 != -1:\n",
    "                ans = min(ans, abs(idx1-idx2))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "\n",
    "        # 方法一、常规做法: 每次记录最近发现的单词的位置\n",
    "        idx1 = -1\n",
    "        idx2 = -1\n",
    "        res = float(\"inf\")\n",
    "        for i, word in enumerate(words):\n",
    "            if word == word1:\n",
    "                idx1 = i\n",
    "            elif word == word2:\n",
    "                idx2 =i\n",
    "\n",
    "            if idx1 >= 0 and idx2 >= 0:\n",
    "                res = min(res, abs(idx2-idx1))\n",
    "        \n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "        ret, i1, i2, n = 100001, -1, -1, len(words)\n",
    "        for i in range(n):\n",
    "            if words[i] == word1:\n",
    "                i1 = i\n",
    "                if i2 > 0:\n",
    "                    ret = min(ret, i1 - i2)\n",
    "            if words[i] == word2:\n",
    "                i2 = i\n",
    "                if i1 > 0:\n",
    "                    ret = min(ret, i2 - i1)\n",
    "        return ret if ret < 100001 else 0\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "        index1 = -1\n",
    "        index2 = -1\n",
    "        ans = -1\n",
    "        for index, word in enumerate(words):\n",
    "            if word == word1:\n",
    "                index1 = index\n",
    "                if index2 != -1:\n",
    "                    if ans == -1:\n",
    "                        ans = abs(index1 - index2)\n",
    "                    else:\n",
    "                        if ans > abs(index1 - index2):\n",
    "                            ans = abs(index1 - index2)\n",
    "\n",
    "            elif word == word2:\n",
    "                index2 = index\n",
    "                if index1 != -1:\n",
    "                    if ans == -1:\n",
    "                        ans = abs(index1 - index2)\n",
    "                    else:\n",
    "                        if ans > abs(index1 - index2):\n",
    "                            ans = abs(index1 - index2)\n",
    "            else:\n",
    "                continue\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "\n",
    "        n = len(words)\n",
    "        res = n\n",
    "        index1, index2 = -1, -1\n",
    "        for i in range(n):\n",
    "            if words[i] == word1:\n",
    "                index1 = i\n",
    "            elif words[i] == word2:\n",
    "                index2 = i\n",
    "            if index1 >= 0 and index2 >= 0:\n",
    "                res = min(res, abs(index1-index2))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "        last_word1, last_word2 = -1, -1\n",
    "\n",
    "        ret = inf\n",
    "        for i in range(len(words)):\n",
    "            if words[i] == word1:\n",
    "                last_word1 = i\n",
    "                if last_word2 > -1:\n",
    "                    ret = min(ret, i - last_word2)\n",
    "            if words[i] == word2:\n",
    "                last_word2 = i\n",
    "                if last_word1 > -1:\n",
    "                    ret = min(ret, i - last_word1)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "        stack=[]\n",
    "        result=float('inf')\n",
    "        for index,value in enumerate(words):\n",
    "            if value==word1 or value==word2:\n",
    "                if stack:\n",
    "                    if stack[-1][1]!=value:\n",
    "                        result=min(result,index-stack[-1][0])\n",
    "                stack.append([index,value])\n",
    "        \n",
    "        return result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "        \n",
    "        res = 100000000\n",
    "        index1,index2=0,0\n",
    "\n",
    "        for i in range(len(words)):\n",
    "            if word1 == words[i]:\n",
    "                index1 = i\n",
    "            elif word2 == words[i]:\n",
    "                index2 = i\n",
    "            print('index1',index1)\n",
    "            print('index2',index2)\n",
    "            if index1 > 0 and index2 > 0:\n",
    "                res = min(res,abs(index1-index2))\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "        dic = {word1:[], word2:[]}\n",
    "        for i in range(len(words)):\n",
    "            if words[i] == word1:   dic[word1].append(i)\n",
    "            elif words[i] == word2:   dic[word2].append(i)\n",
    "        min_res = float(\"inf\")\n",
    "        for i in dic[word1]:\n",
    "            for j in dic[word2]:\n",
    "                if abs(i-j) < min_res:\n",
    "                    min_res = abs(i-j)\n",
    "        return min_res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "        ans = len(words)\n",
    "        index1, index2 = -1, -1\n",
    "        flag = False  # indicates if current index has been updated \n",
    "        for i, word in enumerate(words):\n",
    "            if word == word1:\n",
    "                index1 = i\n",
    "                flag = True \n",
    "            elif word == word2:\n",
    "                index2 = i\n",
    "                flag = True \n",
    "            if flag and index1 >= 0 and index2 >= 0:\n",
    "                ans = min(ans, abs(index1 - index2))\n",
    "                flag = False \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "        ans = len(words)\n",
    "        ind1, ind2 = -1,-1\n",
    "        for i, word in enumerate(words):\n",
    "            if word == word1:\n",
    "                ind1 = i\n",
    "            if word == word2:\n",
    "                ind2 = i\n",
    "            if ind1 >= 0 and ind2 >= 0:\n",
    "                ans = min(ans, abs(ind2-ind1))\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "        def minDistance(a, b):\n",
    "            a = sorted(a)\n",
    "            b = sorted(b)\n",
    "            i, j = 0, 0\n",
    "            ans = float('inf')\n",
    "            while i < len(a) or j < len(b):\n",
    "                if i >= len(a):\n",
    "                    ans = min(ans, abs(a[-1] - b[j]))\n",
    "                    j += 1\n",
    "                elif j >= len(b):\n",
    "                    ans = min(ans, abs(a[i] - b[-1]))\n",
    "                    i += 1\n",
    "                else:\n",
    "                    ans = min(ans, abs(a[i] - b[j]))\n",
    "                    if a[i] > b[j]:\n",
    "                        j += 1\n",
    "                    else:\n",
    "                        i += 1\n",
    "            return ans\n",
    "        dict1 = collections.defaultdict(list)\n",
    "        for idx in range(len(words)):\n",
    "            dict1[words[idx]].append(idx)\n",
    "        return minDistance(dict1[word1], dict1[word2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "        idxs = [-1, -1]\n",
    "        res = len(words)\n",
    "        for i in range(len(words)):\n",
    "            if words[i] == word1:\n",
    "                idxs[0] = i \n",
    "            if words[i] == word2: \n",
    "                idxs[1] = i \n",
    "            if idxs[0]!=-1 and idxs[1]!=-1:\n",
    "                res = min(res, abs(idxs[0]-idxs[1]))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "        len_words = len(words)\n",
    "        word1_id = []\n",
    "        word2_id = []\n",
    "        for i in range(len_words):\n",
    "            if words[i] == word1:\n",
    "                word1_id.append(i)\n",
    "            if words[i] == word2:\n",
    "                word2_id.append(i)\n",
    "        res = len_words\n",
    "        for i in word1_id:\n",
    "            for j in word2_id:\n",
    "                res = min(res, abs(i-j))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "        ans = len(words)\n",
    "        index1, index2 = -1, -1\n",
    "        for i, word in enumerate(words):\n",
    "            if word == word1:\n",
    "                index1 = i\n",
    "            elif word == word2:\n",
    "                index2 = i\n",
    "            if index1 >= 0 and index2 >= 0:\n",
    "                ans = min(ans, abs(index1 - index2))\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "        '''# We can utilise double pointers to localize the two words.\n",
    "        ans=0x7fffffff # Define the greatest hexadecimal number.\n",
    "        a,b=-ans,ans # Label locations of two words using a, b.\n",
    "        for i,j in enumerate(words):\n",
    "            if j==word1:\n",
    "                a=i\n",
    "            elif j==word2:\n",
    "                b=i\n",
    "            ans=min(ans,abs(a-b))\n",
    "        return ans\n",
    "        '''\n",
    "\n",
    "        # Below we utilise Hashtable to mark locations of all words, and then use double pointers to solve the problem.\n",
    "        w=defaultdict(list)\n",
    "        for i,j in enumerate(words):\n",
    "            w[j].append(i)\n",
    "        w1,w2=w[word1],w[word2]\n",
    "        ans=abs(w1[0]-w2[0])\n",
    "        n1,n2=len(w1),len(w2)\n",
    "        i,j=0,0\n",
    "        while i<n1 and j<n2:\n",
    "            if j==n2-1 or (w1[i]<w2[j]):\n",
    "                i+=1\n",
    "            else:\n",
    "                j+=1\n",
    "            if i<n1 and j<n2:\n",
    "                ans=min(ans,abs(w1[i]-w2[j]))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "        pos = defaultdict(list)\n",
    "        for i, word in enumerate(words):\n",
    "            pos[word].append(i)\n",
    "        l1, l2 = pos[word1], pos[word2]\n",
    "        res = float('inf')\n",
    "        for v in l1:\n",
    "            idx = min(len(l2)-1, bisect.bisect_left(l2, v))\n",
    "            pre = max(0, idx-1)\n",
    "            res = min(res, abs(v-l2[idx]), abs(v-l2[pre]))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "[\"I\",\"am\"]\n",
    "\"I\"\n",
    "\"am\"\n",
    "[\"I\",\"am\",\"a\",\"student\",\"from\",\"a\",\"university\",\"in\",\"a\",\"city\"]\n",
    "\"a\"\n",
    "\"student\"\n",
    "\n",
    "words.length <= 100000\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    \"\"\"\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "        res = float('inf')\n",
    "        idx1, idx2 = None, None\n",
    "        for i, w in enumerate(words):\n",
    "            if word1 == w: idx1 = i\n",
    "            elif word2 == w: idx2 = i\n",
    "            if idx1 is not None and idx2 is not None:\n",
    "                res = min(res, abs(idx1-idx2))\n",
    "        return res\n",
    "    \"\"\"\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "        indices = defaultdict(list)\n",
    "        for i, w in enumerate(words):\n",
    "            indices[w].append(i)\n",
    "\n",
    "        index1 = indices[word1]\n",
    "        index2 = indices[word2]\n",
    "        i, j = 0, 0\n",
    "        minDist = float('inf')\n",
    "\n",
    "\n",
    "        while i < len(index1) and j < len(index2):\n",
    "            minDist = min(minDist, abs(index1[i] - index2[j]))\n",
    "\n",
    "            if index1[i] < index2[j]:\n",
    "                i += 1\n",
    "            else:\n",
    "                j += 1\n",
    "\n",
    "        return minDist if minDist != float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "        record = {}\n",
    "        for i, word in enumerate(words):\n",
    "            if word not in record:\n",
    "                record[word] = [i]\n",
    "            else:\n",
    "                record[word].append(i)\n",
    "        a = record[word1]\n",
    "        b = record[word2]\n",
    "        ans = float('inf')\n",
    "        for i in a:\n",
    "            for j in b:\n",
    "                ans = min(ans, abs(i-j))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "        # idx1=-1\n",
    "        # idx2=-1\n",
    "        # ans=float('inf')\n",
    "        # for idx,word in enumerate(words):\n",
    "        #     if word1==word:\n",
    "        #         idx1=idx\n",
    "        #     elif word2==word:\n",
    "        #         idx2=idx\n",
    "        #     if idx1!=-1 and idx2!=-1:\n",
    "        #         ans=min(ans,abs(idx1-idx2))\n",
    "        # return ans\n",
    "        dic=defaultdict(list)\n",
    "        for idx,ele in enumerate(words):\n",
    "            dic[ele].append(idx)\n",
    "        res=len(words)\n",
    "        idx1=0\n",
    "        idx2=0\n",
    "        while idx1<len(dic[word1]) and idx2<len(dic[word2]):\n",
    "            res=min(res,abs(dic[word1][idx1]-dic[word2][idx2]))\n",
    "            if dic[word1][idx1]>dic[word2][idx2]:\n",
    "                idx2+=1\n",
    "            else:\n",
    "                idx1+=1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "        if word1 == word2:\n",
    "            return 0\n",
    "        cache = collections.defaultdict(list)\n",
    "        for i, v in enumerate(words):\n",
    "            cache[v].append(i)\n",
    "        \n",
    "        ids1 = cache[word1]\n",
    "        ids2 = cache[word2]\n",
    "        \n",
    "        res = float('inf')\n",
    "        for i in ids1:\n",
    "            l, r = 0, len(ids2)-1\n",
    "            while l < r:\n",
    "                mid = (l+r+1)//2\n",
    "                if ids2[mid] < i:\n",
    "                    l = mid\n",
    "                else:\n",
    "                    r = mid-1\n",
    "            left = l \n",
    "\n",
    "            l, r = 0, len(ids2)-1\n",
    "            while l < r:\n",
    "                mid = (l+r)//2\n",
    "                if ids2[mid] < i:\n",
    "                    l = mid+1\n",
    "                else:\n",
    "                    r = mid \n",
    "            right = r \n",
    "            \n",
    "            res = min(res, min(abs(i-ids2[left]), abs(ids2[right]-i)))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "        idx_map = defaultdict(list)\n",
    "        for k, v in enumerate(words):\n",
    "            idx_map[v].append(k)\n",
    "        \n",
    "        w1, w2 = idx_map[word1], idx_map[word2]\n",
    "        ans = float('inf')\n",
    "        for idx1 in w1:\n",
    "            for idx2 in w2:\n",
    "                ans = min(ans, abs(idx1-idx2))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "        d = defaultdict(list)\n",
    "        for i in range(len(words)):\n",
    "            d[words[i]].append(i)\n",
    "        res = float('inf')\n",
    "        for i in d[word1]:\n",
    "            for j in d[word2]:\n",
    "                res = min(res, abs(i-j))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "        '''# We can utilise double pointers to localize the two words.\n",
    "        ans=0x7fffffff # Define the greatest hexadecimal number.\n",
    "        a,b=-ans,ans # Label locations of two words using a, b.\n",
    "        for i,j in enumerate(words):\n",
    "            if j==word1:\n",
    "                a=i\n",
    "            elif j==word2:\n",
    "                b=i\n",
    "            ans=min(ans,abs(a-b))\n",
    "        return ans\n",
    "        '''\n",
    "\n",
    "        # Below we utilise Hashtable to mark locations of all words, and then use double pointers to solve the problem.\n",
    "        dic=defaultdict(list)\n",
    "        for value,key in enumerate(words):\n",
    "            dic[key].append(value)\n",
    "        res=len(words)\n",
    "        idx1,idx2=0,0\n",
    "        while idx1<len(dic[word1]) and idx2<len(dic[word2]):\n",
    "            res=min(res,abs(dic[word1][idx1]-dic[word2][idx2]))\n",
    "            if dic[word1][idx1]>dic[word2][idx2]:\n",
    "                idx2+=1\n",
    "            else:\n",
    "                idx1+=1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "        dic = defaultdict(list)\n",
    "        for i in range(len(words)):\n",
    "            dic[words[i]].append(i)\n",
    "        l1 = dic[word1]\n",
    "        l2 = dic[word2]\n",
    "        ans = inf\n",
    "        for v in l1:\n",
    "            for k in l2:\n",
    "                ans = min(ans, abs(v-k))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "        record = collections.defaultdict(list)\n",
    "        for i, word in enumerate(words):\n",
    "            record[word].append(i)\n",
    "        \n",
    "        array1 = record[word1]\n",
    "        array2 = record[word2]\n",
    "        i, j = 0, 0\n",
    "        res = float('inf')\n",
    "        while i < len(array1) and j < len(array2):\n",
    "            res = min(res, abs(array1[i]-array2[j]))\n",
    "            if array1[i] < array2[j]:\n",
    "                i += 1\n",
    "            else:\n",
    "                j += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "        dic = defaultdict(list)\n",
    "        res = float('inf')\n",
    "        for i in range(len(words)):\n",
    "            dic[words[i]].append(i)\n",
    "        if word1 in dic and word2 in dic:\n",
    "            for index1 in dic[word1]:\n",
    "                for index2 in dic[word2]:\n",
    "                    res = min(res,abs(index1-index2))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "        hashMap = {}\n",
    "        for i in range(len(words)):\n",
    "            if words[i] in hashMap:\n",
    "                hashMap[words[i]].append(i)\n",
    "            else:\n",
    "                hashMap[words[i]] = [i]\n",
    "        list1, list2 = hashMap[word1], hashMap[word2]\n",
    "        res, first, second = abs(list1[0] - list2[0]), 0, 0\n",
    "        while first < len(list1):\n",
    "            second = 0\n",
    "            current = abs(list1[first] - list2[second])\n",
    "            while second < len(list2):\n",
    "                temp = abs(list1[first] - list2[second])\n",
    "                if temp > current:\n",
    "                    break\n",
    "                else:\n",
    "                    res = min(res, temp)\n",
    "                    current = temp\n",
    "                second += 1\n",
    "            first += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "        idx_map = defaultdict(list)\n",
    "        for k, v in enumerate(words):\n",
    "            idx_map[v].append(k)\n",
    "        \n",
    "        w1, w2 = idx_map[word1], idx_map[word2]\n",
    "        ans = float('inf')\n",
    "        for idx1 in w1:\n",
    "            for idx2 in w2:\n",
    "                ans = min(ans, abs(idx1-idx2))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def abs(a: int, b: int) -> int :\n",
    "    if a >= b:\n",
    "        return a-b\n",
    "    return b-a\n",
    "\n",
    "class Solution:\n",
    "    def findClosest(self, words: list[str], word1: str, word2: str) -> int:\n",
    "        dict = {}\n",
    "        for i in range(len(words)):\n",
    "            arr = dict.get(words[i], [])\n",
    "            if len(arr) == -0:\n",
    "                dict[words[i]] = []\n",
    "                dict[words[i]].append(i)\n",
    "            else:\n",
    "                dict[words[i]].append(i)\n",
    "        arr1 = dict.get(word1, [])\n",
    "        arr2 = dict.get(word2, [])\n",
    "        if len(arr1) == 0 or len(arr2) == 0:\n",
    "            return -1\n",
    "        r, i, j = len(words),0,0\n",
    "        while i < len(arr1) and j < len(arr2):\n",
    "            d = abs(arr1[i], arr2[j])\n",
    "            if d < r:\n",
    "                r = d\n",
    "            if arr1[i] < arr2[j]:\n",
    "                i += 1\n",
    "            else:\n",
    "                j += 1\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "\n",
    "        # 方法一、常规做法: 一次遍历，每次记录最近发现的单词的位置（之前发现的位置的间距都计算过了，所以可以丢弃）\n",
    "        # idx1 = -1\n",
    "        # idx2 = -1\n",
    "        # res = float(\"inf\")\n",
    "        # for i, word in enumerate(words):\n",
    "        #     if word == word1:\n",
    "        #         idx1 = i\n",
    "        #     elif word == word2:\n",
    "        #         idx2 =i\n",
    "\n",
    "        #     if idx1 >= 0 and idx2 >= 0:\n",
    "        #         res = min(res, abs(idx2-idx1))\n",
    "        \n",
    "        # return res\n",
    "\n",
    "        # 方法二、进阶问题，大文件做法，hash记录位置，双指针遍历一次找距离最小值\n",
    "\n",
    "        lookup = {}\n",
    "        for i, word in enumerate(words):\n",
    "            if word not in lookup:\n",
    "                lookup[word] = []\n",
    "            lookup[word].append(i)\n",
    "        \n",
    "\n",
    "        list1 = lookup[word1]\n",
    "        list2 = lookup[word2]\n",
    "\n",
    "        i, j = 0, 0\n",
    "        res = float(\"inf\")\n",
    "        while i<len(list1) and j<len(list2):\n",
    "            idx1, idx2 = list1[i], list2[j]\n",
    "            res = min(res, abs(idx2-idx1))\n",
    "            if idx1<idx2:\n",
    "                i += 1\n",
    "            else:\n",
    "                j += 1\n",
    "\n",
    "        return res\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "        word2id = {}\n",
    "        for i, word in enumerate(words):\n",
    "            word2id[word] = word2id.get(word, []) + [i]\n",
    "        local_word1 = word2id[word1]\n",
    "        local_word2 = word2id[word2]\n",
    "        res = float('inf')\n",
    "        for i in local_word1:\n",
    "            for j in local_word2:\n",
    "                res = min(res, abs(i-j))\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosest(self, words: List[str], word1: str, word2: str) -> int:\n",
    "        idx_map = defaultdict(list)\n",
    "        for k, v in enumerate(words):\n",
    "            idx_map[v].append(k)\n",
    "        \n",
    "        w1, w2 = idx_map[word1], idx_map[word2]\n",
    "        ans = [abs(i-j) for i in w1 for j in w2]\n",
    "        return sorted(ans)[0]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
